﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TeamFoundation.ContinuousMerge.Collections
{
    /// <summary>
    /// Represents a <see cref="Queue{T}"/> that is safe for use
    /// without locking.
    /// </summary>
    /// <typeparam name="T">The type of each element within the queue.</typeparam>
    public class ConcurrentQueue<T>
    {
        SingleLinkNode<T> head;
        SingleLinkNode<T> tail;

        /// <summary>
        /// Creates a new instance of the <see cref="ConcurrentQueue"/>
        /// class.
        /// </summary>
        public ConcurrentQueue()
        {
            head = new SingleLinkNode<T>();
            tail = head;
        }

        /// <summary>
        /// Enqueues the given item.
        /// </summary>
        /// <param name="item">The item to enqueue.</param>
        public void Enqueue(T item)
        {
            SingleLinkNode<T> oldTail = null;
            SingleLinkNode<T> oldTailNext;

            var newNode = new SingleLinkNode<T>();
            newNode.Item = item;

            bool newNodeWasAdded = false;
            while (!newNodeWasAdded)
            {
                oldTail = tail;
                oldTailNext = oldTail.Next;

                if (tail == oldTail)
                {
                    if (oldTailNext == null)
                        newNodeWasAdded = SyncMethods.CAS(ref tail.Next, null, newNode);
                    else
                        SyncMethods.CAS(ref tail, oldTail, oldTailNext);
                }
            }

            SyncMethods.CAS(ref tail, oldTail, newNode);
        }

        /// <summary>
        /// Attempts to dequeue an item and returns whether the
        /// item was dequeued.
        /// </summary>
        /// <param name="item">The container for the result.</param>
        /// <returns>A value indicating whether an item was dequeued.</returns>
        public bool TryDequeue(out T item)
        {
            item = default(T);
            SingleLinkNode<T> oldHead = null;

            bool haveAdvancedHead = false;
            while (!haveAdvancedHead)
            {
                oldHead = head;
                var oldTail = tail;
                var oldHeadNext = oldHead.Next;

                if (oldHead == head)
                {
                    if (oldHead == oldTail)
                    {
                        if (oldHeadNext == null)
                        {
                            return false;
                        }
                        SyncMethods.CAS(ref tail, oldTail, oldHeadNext);
                    }

                    else
                    {
                        item = oldHeadNext.Item;
                        haveAdvancedHead = SyncMethods.CAS(ref head, oldHead, oldHeadNext);
                    }
                }
            }
            return true;
        }

        /// <summary>
        /// Attempts to dequeue an item and returns
        /// the default value if the queue was empty.
        /// </summary>
        /// <returns>Either the value dequeued. -or- The default value for <typeparamref name="T"/> if no item was in the queue.</returns>
        public T Dequeue()
        {
            T result;
            TryDequeue(out result);
            return result;
        }

        /// <summary>
        /// Attempts to dequeue an item and returns whether the
        /// item was dequeued.
        /// </summary>
        /// <param name="item">The container for the result.</param>
        /// <param name="timeout">The time to wait before returning false.</param>
        /// <returns>A value indicating whether an item was dequeued.</returns>
        public bool TryDequeue(out T item, long timeout)
        {
            long end = Environment.TickCount + timeout;
            do
            {
                if (TryDequeue(out item))
                    return true;
            } while (end >= Environment.TickCount);
            return false;
        }


        /// <summary>
        /// Attempts to dequeue an item and returns whether the
        /// item was dequeued.
        /// </summary>
        /// <param name="item">The container for the result.</param>
        /// <param name="timeout">The time to wait before returning false.</param>
        /// <returns>A value indicating whether an item was dequeued.</returns>
        public bool TryDequeue(out T item, TimeSpan timeout)
        {
            return TryDequeue(out item, timeout.Ticks);
        }
    }
}
